package com.leetcode.solution.s8x;

import java.util.HashMap;
import java.util.Map;

public class Scramble87 {
    public static void main(String[] args) {
        boolean flag = new Scramble87().isScramble("eebaacbcbcadaaedceaaacadccd", "eadcaacabaddaceacbceaabeccd");

        System.out.println(flag);
    }

    private int[][][] cache;
    int N = -1;
    int Y = 1;
    int EMPTY = 0;
    String s1;
    String s2;
    public boolean isScramble(String s1, String s2) {
        this.s1 = s1;
        this.s2 = s2;

        int len = s1.length();
        cache = new int[len][len][len + 1];
        return dfs(0,0, len);
    }

    private boolean dfs(int i, int j, int len) {
        if (cache[i][j][len] != EMPTY) {
            return cache[i][j][len] == Y;
        }

        String subS1 = s1.substring(i, i + len);
        String subS2 = s2.substring(j, j + len);
        if (subS1.equals(subS2)) {
            cache[i][j][len] = Y;
            return true;
        }

        if (!check(i, j, len)) {
            cache[i][j][len] = N;
            return false;
        }

        for (int k = 1; k < len; k++) {
            if (dfs(i, j, k) && dfs(i + k, j + k, len - k)) {
                cache[i][j][len] = Y;
                return true;
            }

            if (dfs(i, j + len - k, k) && dfs(i + k, j, len - k)) {
                cache[i][j][len] = Y;
                return true;
            }

        }

        cache[i][j][len] = N;
        return false;
    }

    private boolean check(int i, int j, int len) {
        Map<Character, Integer> checkMap = new HashMap<Character, Integer>();
        for (int k = i; k < i + len; k++) {
            checkMap.put(s1.charAt(k), checkMap.getOrDefault(s1.charAt(k), 0) + 1);
        }

        for (int k = j; k < j + len; k++) {
            checkMap.put(s2.charAt(k), checkMap.getOrDefault(s2.charAt(k), 0) - 1);
        }

        for (Map.Entry<Character, Integer> characterIntegerEntry : checkMap.entrySet()) {
            if (characterIntegerEntry.getValue() != 0) {
                return false;
            }
        }

        return true;
    }
}
